package com.shuang.dp29;
//
//class Solution {
//    /**
//    * 卖出时支付手续费
//    * @param prices
//    * @param fee
//    * @return
//    */
//    public int maxProfit(int[] prices, int fee) {
//        int len = prices.length;
//        // 0 : 持股
//        // 1 : 不持股
//        // dp 定义第i天持股/不持股 所得最多现金
//        int[][] dp = new int[len][2];
//
//        dp[0][0] = -prices[0];
//
//        for (int i = 1; i < len; i++) {
//            dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] - prices[i]);
//
//            dp[i][1] = Math.max(dp[i - 1][0] + prices[i] - fee, dp[i - 1][1]);
//        }
//
//        return  dp[len - 1][1];
//    }
//
//}

// 一维数组优化
class Solution {
    public int maxProfit(int[] prices, int fee) {

        int[] dp = new int[2];

        dp[0] = -prices[0];
        dp[1] = 0;

        for (int i = 1; i < prices.length; i++) {
            dp[0] = Math.max(dp[0], dp[1] - prices[i]);

            dp[1] = Math.max(dp[1], dp[0] + prices[i] - fee);
        }

        return dp[1];
    }
}